const onRE = /^on[^a-z]/;
const isOn = (key) => onRE.test(key);

const options = {
  // 文本类型节点
  createText(text) {
    return document.createTextNode(text);
  },
  setText(el, text) {
    el.nodeValue = text;
  },
  // 注释节点
  createComment(text) {
    return document.createComment(text);
  },
  createElement(tag) {
    return document.createElement(tag);
  },
  setElementText(el, text) {
    el.textContent = text;
  },
  insert(el, parent, anchor = null) {
    parent.insertBefore(el, anchor);
  },
  patchProps(el, key, prevValue, nextValue) {
    if (isOn(key)) {
      const eventName = key.slice(2).toLowerCase();

      //_vei其实就是vue event invoker的简写，就是一个缓存
      let invokers = el._vei || (el._vei = {});

      // 通过事件名称获取对应的函数
      let invoker = invokers[key];

      if (nextValue) {
        if (!invoker) {
          invoker = el._vei[key] = (e) => {
            // 如果触发事件，早于事件处理函数的绑定时间，就不执行
            if (e.timeStamp < invoker.attached) return;
            // 如果invoker.value是数组，那么就遍历数组，依次执行
            if (Array.isArray(invoker.value)) {
              invoker.value.forEach((fn) => fn(e));
            } else {
              invoker.value(e);
            }
          };
          invoker.value = nextValue;
          // 添加一个存储时间的属性
          invoker.attached = performance.now();
          el.addEventListener(eventName, invoker);
        } else {
          // 如果invoker存在，说明是更新，直接给内部的invoker.value重新赋值
          invoker.value = nextValue;
        }
      } else {
        el.removeEventListener(eventName, invoker);
      }
    } else if (key === "class") {
      el.className = nextValue || "";
    } else if (shouldSetAsProps(el, key, nextValue)) {
      const type = typeof el[key];

      if (type === "boolean" && nextValue === "") {
        el[key] = true;
      } else {
        el[key] = nextValue;
      }
    } else {
      el.setAttribute(key, nextValue);
    }
  },
};

function shouldSetAsProps(el, key, value) {
  if (key === "form" && el.tagName === "INPUT") {
    return false;
  }

  return key in el;
}

// container.innerHTML = "" 清空内容，会存在一些问题
// 在卸载的时候，可能会调用一些其他钩子函数，比如beforeUnmount等生命周期钩子函数
// 组件上可能会存在自定义指令，卸载的时候我们需要正确的去执行这些指令钩子函数
// container.innerHTML = "" 清空内容,不会自动的清空DOM元素上绑定的事件处理函数

// 最好我们通过dom方式给清除掉，而且应该有具体的处理函数

function createRenderer(options) {
  const {
    createText,
    setText,
    createComment,
    createElement,
    setElementText,
    insert,
    patchProps,
  } = options;

  function unmount(vnode) {
    if (vnode.type === Fragment) {
      vnode.children.forEach((child) => {
        unmount(child);
      });
      return;
    }
    const parent = vnode.el.parentNode;
    if (parent) {
      parent.removeChild(vnode.el);
    }
  }

  function render(vnode, container) {
    if (vnode) {
      patch(container._vnode, vnode, container);
    } else {
      if (container._vnode) {
        unmount(container._vnode);
      }
    }

    container._vnode = vnode;
  }

  function patchChildren(oldVnode, newVnode, container) {
    // 如果新子节点的类型是文本节点
    if (typeof newVnode.children === "string") {
      // 如果旧子节点是一组子节点，循环卸载
      if (Array.isArray(oldVnode.children)) {
        oldVnode.children.forEach((child) => {
          unmount(child);
        });
      }

      // 更新文本内容
      setElementText(container, newVnode.children);
    }
    // 如果新子节点是数组，也就是一组子节点
    else if (Array.isArray(newVnode.children)) {
      // 如果旧子节点也是一组子节点
      if (Array.isArray(oldVnode.children)) {
        patchKeyedChildren(oldVnode, newVnode, container);
      }
      // 如果旧子节点是文本节点或者没有子节点
      else {
        setElementText(container, "");

        newVnode.children.forEach((child) => {
          patch(null, child, container);
        });
      }
    }
    // 如果新子节点没有子节点
    else {
      // 如果旧子节点是一组子节点，循环卸载
      if (Array.isArray(oldVnode.children)) {
        oldVnode.children.forEach((child) => {
          unmount(child);
        });
      }
      // 如果旧子节点是文本节点，直接清空文本
      else if (typeof oldVnode.children === "string") {
        setElementText(container, "");
      }
    }
  }

  function patchKeyedChildren(oldVnode, newVnode, container) {
    const oldChildren = oldVnode.children;
    const newChildren = newVnode.children;
    // 处理相同的前置节点，索引j指向新旧两组子节点的开头
    let j = 0;
    let oldVN = oldChildren[j];
    let newVN = newChildren[j];
    // while循环向后遍历，直到遇到拥有不同Key值的节点为止
    while (oldVN.key === newVN.key) {
      // 调用patch函数更新
      patch(oldVN, newVN, container);
      // 更新索引j，递增+1
      j++;
      oldVN = oldChildren[j];
      newVN = newChildren[j];
    }

    // 更新相同的后置节点
    let oldEnd = oldChildren.length - 1;
    let newEnd = newChildren.length - 1;
    oldVN = oldChildren[oldEnd];
    newVN = newChildren[newEnd];

    // while循环从后往前遍历，直到遇到不同key值的节点为止
    while (oldVN.key === newVN.key) {
      // 调用patch函数更新
      patch(oldVN, newVN, container);
      // 递减索引
      oldEnd--;
      newEnd--;
      oldVN = oldChildren[oldEnd];
      newVN = newChildren[newEnd];
    }

    // 满足下面的条件，说明j和newEnd之间的节点需要作为新节点插入
    if (j > oldEnd && j <= newEnd) {
      // 插入的锚点索引
      const anchorIndex = newEnd + 1;
      // 锚点元素，如果锚点索引 >= 新子节点的长度 说明不需要插入，直接挂载到尾部即可
      const anchor =
        anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null;

      // while循环，如果有多个，逐个挂载
      while (j <= newEnd) {
        patch(null, newChildren[j++], container, anchor);
      }
    } else if (j > newEnd && j <= oldEnd) {
      while (j <= oldEnd) {
        unmount(oldChildren[j++]);
      }
    } else {
      // 新子节点中剩余未处理节点的数量
      const count = newEnd - j + 1;
      const source = new Array(count);
      source.fill(-1);
      // 新旧节点的起始索引
      const oldStart = j;
      const newStart = j;
      // 构建索引表
      const keyIndex = {};
      // 新增变量moved和pos
      let moved = false;
      let pos = 0;
      // 新增patched变量，表示更新过的节点数量
      let patched = 0;

      // 索引表中填入键值
      for (let i = newStart; i <= newEnd; i++) {
        keyIndex[newChildren[i].key] = i;
      }
      // 遍历旧节点中未处理的键值
      for (let i = oldStart; i <= oldEnd; i++) {
        oldVN = oldChildren[i];
        // 如果更新过的节点数量<=需要更新的节点数量，执行更新
        if (patched <= count) {
          // 通过索引表快速找到新子节点中具有相同key值的节点位置
          const k = keyIndex[oldVN.key];

          if (typeof k !== "undefined") {
            // 找到了具有相同key值的节点
            newVN = newChildren[k];
            patch(oldVN, newVN, container);
            // 填充source数组
            source[k - newStart] = i;
            // 判断节点是否需要移动
            if (k < pos) {
              moved = true;
            } else {
              pos = k;
            }
          } else {
            // 没有找到,卸载旧节点
            unmount(oldVN);
          }
        } else {
          unmount(oldVN);
        }
      }

      if (moved) {
        const seq = lis(source);

        // s 指向最长递增子序列的最后一个元素
        let s = seq.length - 1;
        // i 指向新的一组子节点的最后一个元素
        let i = count - 1;

        // for 循环 i 递减
        for (; i >= 0; i--) {
          if (source[i] === -1) {
            // 该节点在新子节点中的真实位置索引
            const pos = i + newStart;
            const newVN = newChildren[pos];
            // 该节点的下一个节点的位置索引
            const nextPos = pos + 1;
            // 锚点
            const anchor =
              nextPos < newChildren.length ? newChildren[nextPos].el : null;

            patch(null, newVN, container, anchor);
          } else if (i !== seq[s]) {
            // 如果节点索引i不等于seq[s]的值，说明该节点需要移动
            // 该节点在新的一组子节点中真实位置索引
            const pos = i + newStart;
            const newVN = newChildren[pos];
            // 该节点的下一个节点位置索引
            const nextPos = pos + 1;
            // 锚点
            const anchor =
              nextPos < newChildren.length ? newChildren[nextPos].el : null;
            // 移动
            insert(newVN.el, container, anchor);
          } else {
            // 当i===seq[s]时，说明该位置的节点不需要移动
            // 只需要让s指向下一个位置
            s--;
          }
        }
      }
    }
  }

  function patchElement(oldVnode, newVnode) {
    const el = (newVnode.el = oldVnode.el),
      oldProps = oldVnode.props,
      newProps = newVnode.props;

    // 更新props，如果新的虚拟节点和旧的虚拟节点中属性不一样，进行替换
    for (const key in newProps) {
      if (newProps[key] !== oldProps[key]) {
        patchProps(el, key, oldProps[key], newProps[key]);
      }
    }

    // 如果旧节点中的属性，新节点中没有，将属性值设置为null
    for (const key in oldProps) {
      if (!(key in newProps)) {
        patchProps(el, key, oldProps[key], null);
      }
    }

    //先做属性更新，todo:子节点更新
    patchChildren(oldVnode, newVnode, el);
  }

  function patch(oldVnode, newVnode, container, anchor = null) {
    // 如果旧节点的type和新节点的type不一样，直接卸载旧节点，挂载新节点
    if (oldVnode && oldVnode.type !== newVnode.type) {
      unmount(oldVnode);
      oldVnode = null;
    }

    const { type } = newVnode;

    if (typeof type === "string") {
      // 如果旧节点不存在，就意味着是挂载，调用mountElement函数完成挂载
      if (!oldVnode) {
        mountElement(newVnode, container, anchor);
      } else {
        // 如果oldVnode存在，就是更新, 暂时省略...
        console.log("打补丁");
        patchElement(oldVnode, newVnode);
      }
    } else if (type === Text) {
      // 还是要区分有没有旧节点
      // 如果没有旧节点，直接挂载
      if (!oldVnode) {
        const el = (newVnode.el = createText(newVnode.children));
        // 插入文本节点
        insert(el, container);
      } else {
        const el = (newVnode.el = oldVnode.el);
        if (newVnode.children !== oldVnode.children) {
          setText(el, newVnode.children);
        }
      }
    } else if (type === Comment) {
      // 还是要区分有没有旧节点
      // 如果没有旧节点，直接挂载
      if (!oldVnode) {
        const el = (newVnode.el = createComment(newVnode.children));
        // 插入注释节点
        insert(el, container);
      } else {
        const el = (newVnode.el = oldVnode.el);
        if (newVnode.children !== oldVnode.children) {
          setText(el, newVnode.children);
        }
      }
    } else if (type === Fragment) {
      if (!oldVnode) {
        newVnode.children.forEach((child) => {
          patch(null, child, container);
        });
      } else {
        // 如果oldVnode存在，其实就是更新子节点
        patchChildren(oldVnode, newVnode, container);
      }
    } else if (typeof type === "object") {
      // todo: 组件处理
      console.log("组件处理");
    } else {
      // todo: 未知类型
      console.log("未知类型");
    }
  }

  function mountElement(vnode, container, anchor) {
    // 创建元素
    const el = (vnode.el = createElement(vnode.type));
    if (typeof vnode.children === "string") {
      // 如果子节点是字符串，说明是文本节点，直接挂载
      setElementText(el, vnode.children);
    } else if (Array.isArray(vnode.children)) {
      vnode.children.forEach((child) => {
        patch(null, child, el);
      });
    }

    if (vnode.props) {
      for (const key in vnode.props) {
        const value = vnode.props[key];
        patchProps(el, key, null, value);
      }
    }

    insert(el, container, anchor);
  }

  // 其他可能会用到的函数...
  return {
    render,
    //...其他的函数
  };
}

const isString = (val) => {
  return typeof val === "string";
};

const isObject = (val) => {
  return val !== null && typeof val === "object";
};

const isArray = Array.isArray;

function normalizeClass(value) {
  let res = "";

  if (isString(value)) {
    res = value;
  } else if (isArray(value)) {
    for (let i = 0; i < value.length; i++) {
      const normalized = normalizeClass(value[i]);
      if (normalized) {
        res += normalized + " ";
      }
    }
  } else if (isObject(value)) {
    for (const name in value) {
      if (value[name]) {
        res += name + " ";
      }
    }
  }

  return res;
}

function lis(arr) {
  // 用于记录每个位置的前驱索引，以便最后重建序列
  const p = arr.slice();
  // 存储当前找到的最长递增子序列的索引
  const result = [0];
  // 声明循环变量和辅助变量
  let i, j, u, v, c;
  // 获取输入数组的长度
  const len = arr.length;
  // 遍历输入数组
  for (i = 0; i < len; i++) {
    const arrI = arr[i];
    // 忽略值为 0 的元素（Vue源码中的diff算法对0有特定处理）
    if (arrI !== 0) {
      // 获取当前最长序列中最后一个元素的索引
      j = result[result.length - 1];
      // 贪心算法部分：如果当前元素大于当前最长序列的最后一个元素，直接添加
      if (arr[j] < arrI) {
        // 记录当前元素的前驱索引为 j
        p[i] = j;
        // 将当前元素的索引添加到 result 中
        result.push(i);
        continue;
      }
      // 二分查找部分：在 result 中寻找第一个大于等于 arrI 的元素位置
      u = 0;
      v = result.length - 1;
      while (u < v) {
        // 取中间位置
        c = ((u + v) / 2) | 0;
        // 比较中间位置的值与当前值
        if (arr[result[c]] < arrI) {
          // 如果中间值小于当前值，搜索区间缩小到 [c + 1, v]
          u = c + 1;
        } else {
          // 否则，搜索区间缩小到 [u, c]
          v = c;
        }
      }
      // 如果找到的值大于当前值，进行替换
      if (arrI < arr[result[u]]) {
        // 如果 u 不为 0，记录前驱索引
        if (u > 0) {
          p[i] = result[u - 1];
        }
        // 更新 result 中的位置 u 为当前索引 i
        result[u] = i;
      }
    }
  }
  // 重建最长递增子序列
  u = result.length;
  v = result[u - 1];
  while (u-- > 0) {
    // 将索引替换为对应的前驱索引
    result[u] = v;
    v = p[v];
  }
  // 返回最长递增子序列的索引数组
  return result;
}


const Text = Symbol("Text");
const Comment = Symbol("Comment");
const Fragment = Symbol("Fragment");

const oldVNode = {
  type: "div",
  children: [
    { type: "p", children: "1", key: 1 },
    { type: "p", children: "2", key: 2 },
    { type: "p", children: "3", key: 3 },
    { type: "p", children: "4", key: 4 },
    { type: "p", children: "6", key: 6 },
    { type: "p", children: "5", key: 5 },
  ],
};

const newVNode = {
  type: "div",
  children: [
    { type: "p", children: "1", key: 1 },
    { type: "p", children: "3", key: 3 },
    { type: "p", children: "4", key: 4 },
    { type: "p", children: "2", key: 2 },
    { type: "p", children: "7", key: 7 },
    { type: "p", children: "5", key: 5 },
  ],
};

const renderer = createRenderer(options);
// 首次挂载
renderer.render(oldVNode, document.getElementById("app"));

// 1秒后更新
setTimeout(() => {
  renderer.render(newVNode, document.getElementById("app"));
}, 1000);
